輸送ネットワークは、制限された経路を通る商品、データ、物資の移動をモデル化するための特別な数学的構造です。標準的な有向グラフを、特定の出発点と到着点を指定し、システム内のすべての接続に物理的な「瓶頸」制限を課すことで、機能的なフレームワークへと変換します。
輸送ネットワークの定義
定義10.1.1によれば 定義10.1.1、輸送ネットワーク（単にネットワークとも呼ばれる）とは、単純で重み付きの有向グラフであり、以下の3つの基本条件を満たさなければならない。
性質（a）：ソース
指定された頂点である ソース （$a$ または $s$）は出発点を表します。流入辺が存在せず（入次数 = 0）、無限の供給源として機能します。
性質（b）：シンク
指定された頂点である シンク （$z$ または $t$）は最終消費者を表します。流出辺が存在せず（出次数 = 0）。
性質（c）：容量
各有向辺 $(i, j)$ の重み $C_{ij}$ をその 容量と呼びます。これは非負の数（$C_{ij} \geq 0$）でなければならず、辺がサポートできる最大流量を表します。
現実世界の例：地域電力網
これらの抽象的概念を具体化するために、地域電力網を考えてみましょう：
- ソース： 巨大な水力発電ダム。電力は生成されるのみで、電網からダムに電気が流入することはありません。
- シンク： 大規模工業製造地域。到着した電力を機械の稼働に消費し、電力は電網に戻されることはありません。
- エッジと容量： 送電線がエッジです。その容量は、熱による故障前に物理的な線が耐えられる最大アンペア数です。
- 中間頂点： 電力を消費せずに流れを再配分する地域の変電所（フロー保存則）。
容量とフローの違い
次の2つを明確に区別することが重要です 容量 と フロー。容量 $C_{ij}$ は静的な物理的特性であり、潜在的な体積を表します。一方、フロー $F_{ij}$ は特定の瞬間に移動している実際の体積です。このスライドでは、 構造的制限 容量（構造的制限）に焦点を当てており、現在の移動状態には注目しません。
🎯 核心原則：構造的制約
すべての輸送ネットワークは、供給元（ソース）から消費者（シンク）へと、非負の容量によって制限された経路を通ってフローが移動する有向グラフです。
ソース：$deg^-(a) = 0 \quad | \quad$ シンク：$deg^+(z) = 0 \quad | \quad$ 容量：$C_{ij} \geq 0$